\chapter{Recursividad}
\section{Recursión}
\subsection{Definición}
La recursión una técnica algorítmica donde una operación es definida en base a sí misma; para evitar una recursión infinita definiendo un caso de partida (caso base).

La estructura general de una definición recursiva consta de:

\begin{description}
   \item[Caso base], resolvible usando una expresión simple.
   \item[Caso recursivo], que consta de tres componentes.
   \begin{enumerate}
      \item \textbf{dividir} el problema en partes más pequeñas;
      \item \textbf{llamar} recursivamente así misma para resolver cada parte, y
      \item \textbf{combinar} la solución de las partes para llegar a la solución del problema completo.
   \end{enumerate}
\end{description}

\subsection{Programación Recursiva}
Muchos lenguajes de programación soportan definiciones recursivas (de funciones y estructuras de datos), aunque estas definiciones suelen ser más claras que sus pares iterativos, \emph{pueden} conllevar mayores costos en tiempo y espacio.
\begin{description}
   \item[espacio], el llamado a una función recursiva \emph{puede} requerir espacio adicional para almacenar los parámetros, variables locales y dirección de retorno de cada una de las llamadas recursivas. Por este motivo, la cantidad de información almacenada puede ser proporcional a la cantidad de llamadas recursivas.
   \item[tiempo], las sucesivas asignaciones y desasignaciones de memoria, que implica una llamada recursiva, aporta un tiempo de computación adicional, que también es proporcional al número de llamadas recursivas.
\end{description}

A continuación se muestran algunos ejemplos de problemas simples y una posible solución recursiva.

\begin{enumerate}
   \item La suma de los $n$ primeros naturales 
      \begin{itemize}
      \item Solución algorítmica:

         \begin{description}
            \item [caso base], si $n=1$ la respuesta es $1$.
            \item [caso recursivo], para $n>1$ la respuesta es $n+$"la suma $n-1$ primeros".
         \end{description}

      \item Solución matemática:
         \begin{displaymath}
            sumatoria(n) = 
            \left\{\begin{array}{ll}
               1, & n==1 \\
               sumatoria(n-1), & n>1
            \end{array}\right.
         \end{displaymath}
      \item Implementación en Java.
         \begin{verbatim}
            public class Recursion1{
               public static int sumatoria(int n){
                  if(n == 1) return 1;
                  return n + sumatoria(n - 1);
               }
            }
         \end{verbatim}
      \end{itemize}
   \item Cálculo de $2^n$ con $n \in \mathbf{Z}^+$ 
      \begin{itemize}
         \item Solución algorítmica:
            \begin{description}
               \item[caso base], si $n = 0$ la respuesta es $1$.
               \item[caso recursivo], si $n > 0$ la respuesta es $2$ por $2^{n-1}$.
            \end{description}
         \item Solución matemática:
            \begin{displaymath}
               potencia2(n) =
               \left\{\begin{array}{ll}
                  1, & n==0 \\
                  potencia2(n-1), & n>0
               \end{array}\right.
            \end{displaymath}
         \item Implementación en Java.
            \begin{verbatim}
               public class Recursion2{
                  public static int potencia2(int n){
                     if(n == 0) return 1;
                     return n * potencia2(n-1);
                  }
               }
            \end{verbatim}
      \end{itemize}
\end{enumerate}
\section{Recursión al final}
La recursión al final (\emph{tail recursion}), es una forma especial de recursión donde la última instrucción en la operación es una llamada recursiva. Esta forma especial de recursión puede ser optimizada por el compilador para producir código comparable en espacio, con el producido por una definición iterativa.

El siguiente pseudocódigo muestra la forma general de \emph{tail recursión}.

\begin{math}
   \begin{array}{lll}
      \mbox{\textbf{function}}&foo(n_i)\\
      & \mbox{\textbf{if}}& isDone(n_i) 
         \mbox{ \textbf{then} } \mbox{\textbf{return} } baseCase(n_i)\\
      & \mbox{\textbf{else}} \\
      & &n_{i+1} = transform(n_i)\\
      & &\mbox{\textbf{return }}foo(n_{i+1})
   \end{array}
\end{math}





